
/*
1、题目：lc724. 寻找数组的中心下标:https://leetcode.cn/problems/find-pivot-index/
2、思路： 
        （1）分析问题：
                求中心点： 左边前缀和 == 右边后缀和 - num[i]
        （2）解题思路：
                1、求左边的前缀和，以及 数组总和。
                2、判断 左边的前缀和 == 数组总和sum - 左边的前缀和 - num[i]
        （3）疑惑：
                1、负数会不会影响正确性？
                    因为，prefix[i] = sum - suffix[i]
                    只有前缀计算正确，正负数没有影响
        (4)优化：
                动态求前缀和prefix;
                sum = 2 * prefix + num;
*/
// class Solution {
// public:
//     vector<int> prefix_sum(vector<int> vec){
//         int n = vec.size();
//          vector<int>arr(n,0);
//         if(n <= 0){
//             return vec;
//         }
//         else{
//             arr[0] = vec[0];
//             for(int i = 1; i < n; i++){
//                 arr[i] = arr[i-1] + vec[i];
//             }
//             return arr;
//         }
//     }
//     int pivotIndex(vector<int>& nums) {
//         int sum = accumulate(nums.begin(), nums.end(),0);
//         int n = nums.size();
//         if(n==1){
//             return 0;
//         }
//         auto prefix = prefix_sum(nums);
//         for(auto it : prefix){
//             cout << it <<endl;
//         }
//         for(int i =0; i < n-1; i++){
//             if(i==0){
//                 if(sum-nums[0]==0){
//                     return 0;
//                 }
//             }
//             if(prefix[i]==sum-prefix[i] - nums[i+1]){
//                 return i+1;
//             }
//         }
//         return -1;
//     }
// };
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(),0);
        int prefix = 0;
        for(int i = 0; i < n; i++){
            if(2*prefix + nums[i]== sum){//这里+num[i]是正确的，因为其实nums[i]还没有被计算到prefix中
                return i;
            }
            prefix += nums[i];
        }
        return -1;
    }
};